package com.gxc.linkedList;

import com.gxc.print.ListPrint;

import java.util.*;

/**
 * 2860. 让所有学生保持开心的分组方法数
 * 给你一个下标从 0 开始、长度为 n 的整数数组 nums ，其中 n 是班级中学生的总数。班主任希望能够在让所有学生保持开心的情况下选出一组学生：
 *
 * 如果能够满足下述两个条件之一，则认为第 i 位学生将会保持开心：
 *
 * 这位学生被选中，并且被选中的学生人数 严格大于 nums[i] 。
 * 这位学生没有被选中，并且被选中的学生人数 严格小于 nums[i] 。
 * 返回能够满足让所有学生保持开心的分组方法的数目
 */
public class CountWays {

    public static void main(String[] args) {
        List<Integer> nums = new ArrayList<>();
        nums.add(2);
        nums.add(2);
        ListPrint.print(nums);
        nums.sort((o1, o2) -> o1 - o2);
        ListPrint.print(nums);
        System.out.println(handle(nums));
    }

    public static int handle(List<Integer> nums) {
        int n = nums.size();
        int res = 0;
        Collections.sort(nums);
        for (int k = 0; k <= n; k++) {
            // 前 k 个元素的最大值是否小于 k
            if (k > 0 && nums.get(k - 1) >= k) {
                continue;
            }
            // 后 n - k 个元素的最小值是否大于 k
            if (k < n && nums.get(k) <= k) {
                continue;
            }
            res++;
        }
        return res;
    }

    /**
     * 所有满足 nums[i]<k 的学生应被选中；
     *
     * 所有满足 nums[i]>k 的学生不应被选中；
     *
     * 不能存在 nums[i]=k 的学生；
     *
     *  nums 从小到大排序。我们枚举选中的人数 k，由于 nums 已有序，
     *  此时最优分组一定是前 k 个学生被选中，剩余的 n−k 个学生不被选中，
     *  此时只需要检测选中的 k 个学生中的最大值是否满足小于 k，
     *  未被选中的学生中的最小值是否满足大于 k 即可，
     *  如果同时满足上述两个条件，则该分配方案可行，
     *  最终返回可行的方案计数即可，需要注意处理好边界 0 与 n
     *

     */
    class Solution {
        public int countWays(List<Integer> nums) {
            int n = nums.size();
            int res = 0;
            Collections.sort(nums);
            for (int k = 0; k <= n; k++) {
                // 前 k 个元素的最大值是否小于 k
                if (k > 0 && nums.get(k - 1) >= k) {
                    continue;
                }
                // 后 n - k 个元素的最小值是否大于 k
                if (k < n && nums.get(k) <= k) {
                    continue;
                }
                res++;
            }
            return res;
        }
    }


}
